Exercise: Skiplists

Solve a task to modify the find(x) method in a skiplist.

We'll cover the following

Task#

The find(x) method in a Skiplist sometimes performs redundant comparisons; these occur when x is compared to the same value more than once. They can occur when, for some node, u, u.next[r] = u.next[r − 1]. Modify the find(x) so that these redundant comparisons are avoided.

Sample input

The sample input will be as follows:

The first 25 values in a skiplist will be using this formula: i % 100 + 900
The next 50 values in a skiplist will be using this formula: i % 50
The next 25 values in a skiplist will be using this formula: i % 20

Expected output

The expected output will be as follows:

Adding 1000 elements
Searching
Found: 10 , 20 , None

Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.

Good luck!

svg viewer

Note: You must implement the method find_pred_node() in the below code starting at line 31.

main.py
base.py
utils.py
Solution to implement an efficient find() method

Discussion on Skiplists

Solution: Skiplists